
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
 * 例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB
 * User: 86187
 * Date: 2022-10-06
 * Time: 21:03
 */
public class Test {
    // map 用于去重 key 和 val存放的值一样 方便取出key值.
    private static final Map<String,String> map = new HashMap<>();
    // 交换
    private static void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
    private static void PermutationHelper(char[] str,int start,ArrayList<String> result,int length) {
        if(start == str.length - 1){
            String s = new String(str); // 注意深浅拷贝 所以新new了一个String对象
            if(map.isEmpty() || !map.containsKey(s)) {
                map.put(s,s);
                result.add(map.get(s));
            }
        }
        for (int i = start; i < length; i++) {
            // start永远代表第一个,谁和start交换 谁就是第一个
            swap(str,start,i);
            // 将str[i]对应字符开头的情况 排列并去重后 放到result中.
            PermutationHelper(str,start+1,result,length);
            // 将字符数组恢复为 [a,b,c].
            swap(str,start,i);
        }
    }
    public static ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        if(str != null && str.length() != 0) {
            int length = str.length();
            PermutationHelper(str.toCharArray(),0,result,length);
            // 排序: 默认升序
            Collections.sort(result);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Permutation("abc"));
    }
}
